// Copyright 2012 Google Inc. All Rights Reserved.  -*- C++ -*-
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/// \file range

#ifndef STD_RANGE
#define STD_RANGE

#include <cassert>
#include <array>
#include <iterator>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

namespace std {

// Nothing in this namespace is part of the exported interface.
namespace detail {
/// Used as the result type of undefined functions.
struct undefined {};

template<typename R>
class begin_result {
  template<typename T>
  static auto check(T&& t) -> decltype(begin(t));
  static undefined check(...);
public:
  typedef decltype(check(declval<R>())) type;
};
template<typename R>
class end_result {
  template<typename T>
  static auto check(T&& t) -> decltype(end(t));
  static undefined check(...);
public:
  typedef decltype(check(declval<R>())) type;
};

// Things that begin and end work on, in compatible ways, are
// ranges. [stmt.ranged]
template<typename R>
struct is_range : is_same<typename detail::begin_result<R>::type,
                          typename detail::end_result<R>::type> {};

// This currently requires specialization and doesn't work for
// detecting \c range<>s or iterators.  We should add
// \c contiguous_iterator_tag to fix that.
template<typename R>
struct is_contiguous_range : false_type {};
template<typename R>
struct is_contiguous_range<R&> : is_contiguous_range<R> {};
template<typename R>
struct is_contiguous_range<R&&> : is_contiguous_range<R> {};
template<typename R>
struct is_contiguous_range<const R> : is_contiguous_range<R> {};

template<typename T, size_t N>
struct is_contiguous_range<T[N]> : true_type {};
template<typename T, size_t N>
struct is_contiguous_range<const T[N]> : true_type {};
template<typename T, size_t N>
struct is_contiguous_range<array<T, N>> : true_type {};
template<typename charT, typename traits, typename Allocator>
struct is_contiguous_range<basic_string<charT, traits, Allocator>> : true_type {};
template<typename T, typename Allocator>
struct is_contiguous_range<vector<T, Allocator>> : true_type {};

// Removes cv qualifiers from all levels of a multi-level pointer
// type, not just the type level.
template<typename T>
struct remove_all_cv_ptr { typedef T type; };
template<typename T>
struct remove_all_cv_ptr<T*> { typedef typename remove_all_cv_ptr<T>::type* type; };
template<typename T>
struct remove_all_cv_ptr<const T> { typedef typename remove_all_cv_ptr<T>::type type; };
template<typename T>
struct remove_all_cv_ptr<volatile T> { typedef typename remove_all_cv_ptr<T>::type type; };
template<typename T>
struct remove_all_cv_ptr<const volatile T> { typedef typename remove_all_cv_ptr<T>::type type; };

template<typename From, typename To>
struct conversion_preserves_array_indexing : false_type {};
template<typename FromVal, typename ToVal>
struct conversion_preserves_array_indexing<FromVal*, ToVal*>
  : integral_constant<bool,
                      is_convertible<FromVal*, ToVal*>::value &&
                      is_same<typename remove_all_cv_ptr<FromVal>::type,
                              typename remove_all_cv_ptr<ToVal>::type>::value> {};

template<typename T>
constexpr auto adl_begin(T&& t) -> decltype(begin(t)) { return begin(forward<T>(t)); }
template<typename T>
constexpr auto adl_end(T&& t) -> decltype(end(t)) { return end(forward<T>(t)); }
}

/// A \c std::range<Iterator> represents a half-open iterator range
/// built from two iterators, \c 'begin', and \c 'end'.  If \c end is
/// not reachable from \c begin, the behavior is undefined.
///
/// The mutability of elements of the range is controlled by the
/// Iterator argument.  Instantiate
/// <code>range<<var>Foo</var>::iterator></code> or
/// <code>range<<var>T</var>*></code>, or call
/// <code>make_range(<var>non_const_container</var>)</code>, and you
/// get a mutable range.  Instantiate
/// <code>range<<var>Foo</var>::const_iterator></code> or
/// <code>range<const <var>T</var>*></code>, or call
/// <code>make_range(<var>const_container</var>)</code>, and you get a
/// constant range.
///
/// \todo Inherit from std::pair<Iterator, Iterator>?
///
/// \todo This interface contains some functions that could be
/// provided as free algorithms rather than member functions, and all
/// of the <code>pop_*()</code> functions could be replaced by \c
/// slice() at the cost of some extra iterator copies.  This makes
/// them more awkward to use, but makes it easier for users to write
/// their own types that follow the same interface. On the other hand,
/// a \c range_facade could be provided to help users write new
/// ranges, and it could provide the members.  Such functions are
/// marked with a note in their documentation.  (Of course, all of
/// these member functions could be provided as free functions using
/// the iterator access methods, but one goal here is to allow people
/// to program without touching iterators at all.)
template<typename Iterator>
class range {
  Iterator begin_, end_;
 public:
  /// \name types
  /// @{

  /// The iterator category of \c Iterator.
  /// \todo Consider defining range categories. If they don't add
  /// anything over the corresponding iterator categories, then
  /// they're probably not worth defining.
  typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
  /// The type of elements of the range. Not cv-qualified.
  typedef typename iterator_traits<Iterator>::value_type value_type;
  /// The type of the size of the range and offsets within the range.
  typedef typename iterator_traits<Iterator>::difference_type difference_type;
  /// The return type of element access methods: \c front(), \c back(), etc.
  typedef typename iterator_traits<Iterator>::reference reference;
  typedef typename iterator_traits<Iterator>::pointer pointer;
  /// @}

  /// \name constructors
  /// @{

  /// Creates a range of default-constructed (<em>not</em>
  /// value-initialized) iterators.  For most \c Iterator types, this
  /// will be an invalid range.
  range() = default;

  /// \pre \c end is reachable from \c begin.
  /// \post <code>this->begin() == begin && this->end() == end</code>
  constexpr range(Iterator begin, Iterator end)
      : begin_(begin), end_(end) {}

  /// \par Participates in overload resolution if:
  ///   - \c Iterator is not a pointer type,
  ///   - \c begin(r) and \c end(r) return the same type, and
  ///   - that type is convertible to \c Iterator.
  ///
  /// \todo std::begin and std::end are overloaded between T& and
  /// const T&, which means that if a container has only a non-const
  /// begin or end method, then it's ill-formed to pass an rvalue to
  /// the free function.  To avoid that problem, we don't use
  /// std::forward<> here, so begin() and end() are always called with
  /// an lvalue.  Another option would be to insist that rvalue
  /// arguments to range() must have const begin() and end() methods.
  template<typename R>
  constexpr range(R&& r,
                  typename enable_if<!is_pointer<Iterator>::value &&
                                     detail::is_range<R>::value &&
                                     is_convertible<typename detail::begin_result<R>::type,
                                                    Iterator>::value
                                     >::type* =0)
    : begin_(detail::adl_begin(r)), end_(detail::adl_end(r)) {}

  /// This constructor creates a \c range<T*> from any range with
  /// contiguous iterators. Because dereferencing a past-the-end
  /// iterator can be undefined behavior, empty ranges get initialized
  /// with \c nullptr rather than \c &*begin().
  ///
  /// \par Participates in overload resolution if:
  ///   - \c Iterator is a pointer type \c T*,
  ///   - \c begin(r) and \c end(r) return the same type,
  ///   - elements \c i of that type satisfy the invariant
  ///     <code>&*(i + N) == (&*i) + N</code>, and
  ///   - The result of <code>&*begin()</code> is convertible to \c T*
  ///     using only qualification conversions [conv.qual] (since
  ///     pointer conversions stop the pointer from pointing to an
  ///     array element).
  ///
  /// \todo The <code>&*(i + N) == (&*i) + N</code> invariant is
  /// currently impossible to check for user-defined types.  We need a
  /// \c contiguous_iterator_tag to let users assert it.
  template<typename R>
  constexpr range(R&& r,
                  typename enable_if<is_pointer<Iterator>::value &&
                                     detail::is_contiguous_range<R>::value &&
                                     detail::conversion_preserves_array_indexing<
                                       decltype(&*detail::adl_begin(r)),
                                       Iterator>::value
                                     >::type* =0)
    : begin_((detail::adl_begin(r) == detail::adl_end(r) &&
              !is_pointer<decltype(detail::adl_begin(r))>::value)
             // For non-pointers, &*begin(r) is only defined behavior
             // if there's an element there.  Otherwise, use nullptr
             // since the user can't dereference it anyway.  This _is_
             // detectable.
             ? nullptr : &*detail::adl_begin(r)),
      end_(begin_ + (detail::adl_end(r) - detail::adl_begin(r))) {}

  /// @}

  /// \name iterator access
  /// @{
  constexpr Iterator begin() const { return begin_; }
  constexpr Iterator end() const { return end_; }
  /// @}

  /// \name element access
  /// @{

  /// \par Complexity:
  /// O(1)
  /// \pre \c !empty()
  /// \returns a reference to the element at the front of the range.
  constexpr reference front() const { return *begin(); }

  /// \par Ill-formed unless:
  /// \c iterator_category is convertible to \c
  /// bidirectional_iterator_tag.
  ///
  /// \par Complexity:
  /// O(2) (Involves copying and decrementing an iterator, so not
  /// quite as cheap as \c front())
  ///
  /// \pre \c !empty()
  /// \returns a reference to the element at the front of the range.
  constexpr reference back() const {
    static_assert(is_convertible<iterator_category, bidirectional_iterator_tag>::value,
                  "Can only retrieve the last element of a bidirectional range.");
    return *prev(end());
  }

  /// This method is drawn from scripting language indexing.  It
  /// indexes forward from the beginning of the range if the argument
  /// is positive, or backwards from the end of the array if the
  /// argument is negative.
  ///
  /// \par Ill-formed unless:
  /// \c iterator_category is convertible to \c
  /// random_access_iterator_tag.
  ///
  /// \par Complexity:
  /// O(1)
  ///
  /// \pre <code>abs(index) < size() || index == -size()</code>
  ///
  /// \returns if <code>index >= 0</code>, a reference to the
  /// <code>index</code>'th element in the range. Otherwise, a
  /// reference to the <code>size()+index</code>'th element.
  constexpr reference operator[](difference_type index) const {
    static_assert(is_convertible<iterator_category, random_access_iterator_tag>::value,
                  "Can only index into a random-access range.");
    // Less readable construction for constexpr support.
    return index < 0 ? end()[index]
                     : begin()[index];
  }
  /// @}

  /// \name size
  /// @{

  /// \par Complexity:
  /// O(1)
  /// \returns \c true if the range contains no elements.
  constexpr bool empty() const { return begin() == end(); }

  /// \par Ill-formed unless:
  /// \c iterator_category is convertible to
  /// \c forward_iterator_tag.
  ///
  /// \par Complexity:
  /// O(1) if \c iterator_category is convertible to \c
  /// random_access_iterator_tag. O(<code>size()</code>)
  /// otherwise.
  ///
  /// \returns the number of times \c pop_front() can be called before
  /// \c empty() becomes true.
  constexpr difference_type size() const {
    static_assert(is_convertible<iterator_category, forward_iterator_tag>::value,
                  "Calling size on an input range would destroy the range.");
    return dispatch_size(iterator_category());
  }
  /// @}

  /// \name traversal from the beginning of the range
  /// @{

  /// Advances the beginning of the range by one element.
  /// \pre \c !empty()
  void pop_front() { ++begin_; }

  /// Advances the beginning of the range by \c n elements.
  ///
  /// \par Complexity:
  /// O(1) if \c iterator_category is convertible to \c
  /// random_access_iterator_tag, O(<code>n</code>) otherwise.
  ///
  /// \pre <code>n >= 0</code>, and there must be at least \c n
  /// elements in the range.
  void pop_front(difference_type n) {
    advance(begin_, n);
  }

  /// Advances the beginning of the range by at most \c n elements,
  /// stopping if the range becomes empty.  A negative argument causes
  /// no change.
  ///
  /// \par Complexity:
  /// O(1) if \c iterator_category is convertible to \c
  /// random_access_iterator_tag, O(<code>min(n,
  /// <var>#-elements-in-range</var>)</code>) otherwise.
  ///
  /// \note Could be provided as a free function with little-to-no
  /// loss in efficiency.
  void pop_front_upto(difference_type n) {
    advance_upto(begin_, max<difference_type>(0, n), end_,
                 iterator_category());
  }

  /// @}

  /// \name traversal from the end of the range
  /// @{

  /// Moves the end of the range earlier by one element.
  ///
  /// \par Ill-formed unless:
  /// \c iterator_category is convertible to
  /// \c bidirectional_iterator_tag.
  ///
  /// \par Complexity:
  /// O(1)
  ///
  /// \pre \c !empty()
  void pop_back() {
    static_assert(is_convertible<iterator_category, bidirectional_iterator_tag>::value,
                  "Can only access the end of a bidirectional range.");
    --end_;
  }

  /// Moves the end of the range earlier by \c n elements.
  ///
  /// \par Ill-formed unless:
  /// \c iterator_category is convertible to
  /// \c bidirectional_iterator_tag.
  ///
  /// \par Complexity:
  /// O(1) if \c iterator_category is convertible to \c
  /// random_access_iterator_tag, O(<code>n</code>) otherwise.
  ///
  /// \pre <code>n >= 0</code>, and there must be at least \c n
  /// elements in the range.
  void pop_back(difference_type n) {
    static_assert(is_convertible<iterator_category, bidirectional_iterator_tag>::value,
                  "Can only access the end of a bidirectional range.");
    advance(end_, -n);
  }

  /// Moves the end of the range earlier by <code>min(n,
  /// size())</code> elements.  A negative argument causes no change.
  ///
  /// \par Ill-formed unless:
  /// \c iterator_category is convertible to
  /// \c bidirectional_iterator_tag.
  ///
  /// \par Complexity:
  /// O(1) if \c iterator_category is convertible to \c
  /// random_access_iterator_tag, O(<code>min(n,
  /// <var>#-elements-in-range</var>)</code>) otherwise.
  ///
  /// \note Could be provided as a free function with little-to-no
  /// loss in efficiency.
  void pop_back_upto(difference_type n) {
    static_assert(is_convertible<iterator_category, bidirectional_iterator_tag>::value,
                  "Can only access the end of a bidirectional range.");
    advance_upto(end_, -max<difference_type>(0, n), begin_,
                 iterator_category());
  }

  /// @}

  /// \name creating derived ranges
  /// @{

  /// Divides the range into two pieces at \c index, where a positive
  /// \c index represents an offset from the beginning of the range
  /// and a negative \c index represents an offset from the end.
  /// <code>range[index]</code> is the first element in the second
  /// piece.  If <code>index >= size()</code>, the second piece
  /// will be empty. If <code>index < -size()</code>, the first
  /// piece will be empty.
  ///
  /// \par Ill-formed unless:
  /// \c iterator_category is convertible to
  /// \c forward_iterator_tag.
  ///
  /// \par Complexity:
  ///   - If \c iterator_category is convertible to \c
  ///     random_access_iterator_tag: O(1)
  ///   - Otherwise, if \c iterator_category is convertible to \c
  ///     bidirectional_iterator_tag, \c abs(index) iterator increments
  ///     or decrements
  ///   - Otherwise, if <code>index >= 0</code>,  \c index iterator
  ///     increments
  ///   - Otherwise, <code>size() + (size() + index)</code>
  ///     iterator increments.
  ///
  /// \returns a pair of adjacent ranges.
  ///
  /// \post
  ///   - <code>result.first.size() == min(index, this->size())</code>
  ///   - <code>result.first.end() == result.second.begin()</code>
  ///   - <code>result.first.size() + result.second.size()</code> <code>==
  ///     this->size()</code>
  ///
  /// \todo split() could take an arbitrary number of indices and
  /// return an <code>N+1</code>-element \c tuple<>. This is tricky to
  /// implement with negative indices in the optimal number of
  /// increments or decrements for a bidirectional iterator, but it
  /// should be possible.  Do we want it?
  pair<range, range> split(difference_type index) const {
    static_assert(is_convertible<iterator_category, forward_iterator_tag>::value,
                  "Calling split on a non-forward range would return a useless first result.");
    if (index >= 0) {
      range second = *this;
      second.pop_front_upto(index);
      return make_pair(range(begin(), second.begin()), second);
    } else {
      return dispatch_split_neg(index, iterator_category());
    }
  }

  /// \returns A sub-range from \c start to \c stop (not including \c
  /// stop, as usual).  \c start and \c stop are interpreted as for
  /// <code>operator[]</code>, with negative values offsetting from
  /// the end of the range.  Omitting the \c stop argument makes the
  /// sub-range continue to the end of the original range. Positive
  /// arguments saturate to the end of the range, and negative
  /// arguments saturate to the beginning.  If \c stop is before \c
  /// start, returns an empty range beginning and ending at \c start.
  ///
  /// \par Ill-formed unless:
  /// \c iterator_category is convertible to
  /// \c forward_iterator_tag.
  ///
  /// \par Complexity:
  ///   - If \c iterator_category is convertible to \c
  ///     random_access_iterator_tag: O(1)
  ///   - Otherwise, if \c iterator_category is convertible to \c
  ///     bidirectional_iterator_tag, at most <code>min(abs(start),
  ///     size()) + min(abs(stop), size())</code> iterator
  ///     increments or decrements
  ///   - Otherwise, if <code>start >= 0 && stop >= 0</code>,
  ///     <code>max(start, stop)</code> iterator increments
  ///   - Otherwise, <code>size() + max(start', stop')</code>
  ///     iterator increments, where \c start' and \c stop' are the
  ///     offsets of the elements \c start and \c stop refer to.
  ///
  /// \note \c slice(start) should be implemented with a different
  /// overload, rather than defaulting \c stop to
  /// <code>numeric_limits<difference_type>::max()</code>, because
  /// using a default would force non-random-access ranges to use an
  /// O(<code>size()</code>) algorithm to compute the end rather
  /// than the O(1) they're capable of.
  range slice(difference_type start, difference_type stop) const {
    static_assert(is_convertible<iterator_category, forward_iterator_tag>::value,
                  "Calling slice on a non-forward range would destroy the original range.");
    return dispatch_slice(start, stop, iterator_category());
  }

  range slice(difference_type start) const {
    static_assert(is_convertible<iterator_category, forward_iterator_tag>::value,
                  "Calling slice on a non-forward range would destroy the original range.");
    return split(start).second;
  }

  /// @}

private:
  // advance_upto: should be added to <algorithm>, but I'll use it as
  // a helper function here.
  //
  // These return the number of increments that weren't applied
  // because we ran into 'limit' (or 0 if we didn't run into limit).
  static difference_type advance_upto(Iterator& it, difference_type n,
                                      Iterator limit,
                                      input_iterator_tag) {
    if (n < 0)
      return 0;
    while (it != limit && n > 0) {
      ++it;
      --n;
    }
    return n;
  }
  static difference_type advance_upto(Iterator& it, difference_type n,
                                      Iterator limit,
                                      bidirectional_iterator_tag) {
    if (n < 0) {
      while (it != limit && n < 0) {
        --it;
        ++n;
      }
    } else {
      while (it != limit && n > 0) {
        ++it;
        --n;
      }
    }
    return n;
  }
  static difference_type advance_upto(Iterator& it, difference_type n,
                                      Iterator limit,
                                      random_access_iterator_tag) {
    difference_type distance = limit - it;
    if (distance < 0) assert(n <= 0);
    else if (distance > 0) assert(n >= 0);

    if (abs(distance) > abs(n)) {
      it += n;
      return 0;
    } else {
      it = limit;
      return n - distance;
    }
  }

  // Dispatch functions.
  difference_type dispatch_size(forward_iterator_tag) const {
    return std::distance(begin(), end());
  }
  constexpr difference_type dispatch_size(random_access_iterator_tag) const {
    return end() - begin();
  }

  pair<range, range> dispatch_split_neg(difference_type index,
                                        forward_iterator_tag) const {
    assert(index < 0);
    difference_type size = this->size();
    return split(max<difference_type>(0, size + index));
  }
  pair<range, range> dispatch_split_neg(difference_type index,
                                        bidirectional_iterator_tag) const {
    assert(index < 0);
    range first = *this;
    first.pop_back_upto(-index);
    return make_pair(first, range(first.end(), end()));
  }

  range dispatch_slice(difference_type start, difference_type stop,
                       forward_iterator_tag) const {
    if (start < 0 || stop < 0) {
      difference_type size = this->size();
      if (start < 0)
        start = max<difference_type>(0, size + start);
      if (stop < 0)
        stop = size + stop;  // Possibly negative; will be fixed in 2 lines.
    }
    stop = max<difference_type>(start, stop);

    Iterator first = begin();
    advance_upto(first, start, end(), iterator_category());
    Iterator last = first;
    advance_upto(last, stop - start, end(), iterator_category());
    return range(first, last);
  }
  range dispatch_slice(const difference_type start, const difference_type stop,
                       bidirectional_iterator_tag) const {
    Iterator first;
    if (start < 0) {
      first = end();
      advance_upto(first, start, begin(), iterator_category());
    } else {
      first = begin();
      advance_upto(first, start, end(), iterator_category());
    }
    Iterator last;
    if (stop < 0) {
      last = end();
      advance_upto(last, stop, first, iterator_category());
    } else {
      if (start >= 0) {
        last = first;
        if (stop > start)
          advance_upto(last, stop - start, end(), iterator_category());
      } else {
        // Complicated: 'start' walked from the end of the sequence,
        // but 'stop' needs to walk from the beginning. 
        Iterator dummy = begin();
        // Walk up to 'stop' increments from begin(), stopping when we
        // get to 'first', and capturing the remaining number of
        // increments.
        difference_type increments_past_start =
          advance_upto(dummy, stop, first, iterator_category());
        if (increments_past_start == 0) {
          // If this is 0, then stop was before start.
          last = first;
        } else {
          // Otherwise, count that many spaces beyond first.
          last = first;
          advance_upto(last, increments_past_start, end(),
                        iterator_category());
        }
      }
    }
    return range(first, last);
  }
  range dispatch_slice(difference_type start, difference_type stop,
                       random_access_iterator_tag) const {
    const difference_type size = this->size();
    if (start < 0)
      start = size + start;
    if (start < 0)
      start = 0;
    if (start > size)
      start = size;

    if (stop < 0)
      stop = size + stop;
    if (stop < start)
      stop = start;
    if (stop > size)
      stop = size;

    return range(begin() + start, begin() + stop);
  }
};

/// \name deducing constructor wrappers
/// \relates std::range
/// \xmlonly <nonmember/> \endxmlonly
///
/// These functions do the same thing as the constructor with the same
/// signature. They just allow users to avoid writing the iterator
/// type.
/// @{

/// \todo I'd like to define a \c make_range taking a single iterator
/// argument representing the beginning of a range that ends with a
/// default-constructed \c Iterator.  This would help with using
/// iterators like \c istream_iterator.  However, using just \c
/// make_range() could be confusing and lead to people writing
/// incorrect ranges of more common iterators. Is there a better name?
template<typename Iterator>
constexpr range<Iterator> make_range(Iterator begin, Iterator end) {
  return range<Iterator>(begin, end);
}

/// \par Participates in overload resolution if:
/// \c begin(r) and \c end(r) return the same type.
template<typename Range>
constexpr auto make_range(Range&& r,
                          typename enable_if<detail::is_range<Range>::value>::type* =0)
    -> range<decltype(begin(r))> {
  return range<decltype(begin(r))>(r);
}

/// \par Participates in overload resolution if:
///   - \c begin(r) and \c end(r) return the same type,
///   -  that type satisfies the invariant that <code>&*(i + N) ==
///      (&*i) + N</code>, and
///   - \c &*begin(r) has a pointer type.
template<typename Range>
constexpr auto make_ptr_range(Range&& r,
                              typename enable_if<detail::is_contiguous_range<Range>::value &&
                                                 is_pointer<decltype(&*begin(r))>::value>::type* =0)
    -> range<decltype(&*begin(r))> {
  return range<decltype(&*begin(r))>(r);
}

/// @}

}      // End namespace

#endif  // STD_RANGE
